//  两数之和 II - 输入有序数组

package Leetcode;

class Solution167_1 {
    public int[] twoSum(int[] numbers, int target) {
        for (int first = 0; first < numbers.length - 1; first++) {
            int second = target - numbers[first];
            // 二分查找
            int left = first + 1;
            int right = numbers.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (numbers[mid] == second)
                    return new int[] { first + 1, mid + 1 };
                else if (numbers[mid] < second) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } // while
        } // for
        return new int[2];
    }
}

class Solution167_2 {
    public int[] twoSum(int[] numbers, int target) {
        int font = 0;
        int back = numbers.length - 1;
        while (font < back) {
            if (numbers[font] + numbers[back] == target)
                return new int[] { font + 1, back + 1 };
            else if (numbers[font] + numbers[back] > target)
                back--;
            else
                font++;
        }
        return new int[2];
    }
}